# Сочетания

_Сочетания из n объектов по k_ — это возможные варианты выбора _k_ различных элементов из _n_ объектов 
без учета порядка расположения этих элементов. 
Приведем пример сочетаний из пяти объектов _{a, b, c, d, e}_ по три:
_abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde_.

Подсчитать общее число сочетаний из _n_ объектов по _k_ можно так: 
существует _n(n − 1)...(n − k + 1)_ способов выбора первых _k_ объектов в перестановке, 
причем каждое сочетание из _k_ элементов встречается ровно _k!_ раз, 
так как для любого набора из _k_ объектов существует _k!_ перестановок. 
Поэтому для числа сочетаний из _n_ элементов по _k_, которое мы обозначим через \\(\binom{n}{k}\\), 
получаем следующую формулу: 

**Формула 1**: \\(\binom{n}{k} = \frac{n(n - 1)...(n - k + 1)}{k(k - 1)...(1)}\\)

Величины \\(\binom{n}{k}\\) (читается “число сочетаний из n по k”) называются _биномиальными коэффициентами_.

**Алгоритм:**

- Если `k` меньше `0` или больше `n`, то число сочетаний равно `0`
- Если `k` больше половины `n`, то воспользуемся _Свойством симметрии (Формула 3 ниже)_, 
  чтобы уменьшить количество операций
- Устанавливаем переменные `num` (числитель) и `den` (знаменатель) равными `1`
- Выполняем итерацию по каждому `i` от `0` до `k`:
    - `num` умножаем на `n - i`, а `den` - на `k - i`
    - Переходим к следующей итерации
- Число сочетаний равно `num/den`

**Оценка:**

- **Время** - O(k)
- **Память** - O(1)

**Код:**

```dotty
@tailrec
def binomialCoefficient(n: Int, k: Int): BigInt =
  if k < 0 || k > n then BigInt(0)
  else if k > (n / 2) then binomialCoefficient(n, n - k)
  else
    val (num, den) = (0 until k).foldLeft((BigInt(1), BigInt(1))) {
      case ((num, den), i) =>
        (num * BigInt(n - i), den * BigInt(k - i))
    }
    num / den
    
binomialCoefficient(100, 32)
// BigInt("143012501349174257560226775")    
```

**Метрики:**

Вычисление числа сочетаний из 100000 по 50000 занимает примерно 5,5 секунд.

```dotty
@main def binomialCoefficientBench(): BigInt =
  binomialCoefficient(100000, 50000)
      
// CPU Time: 5537 ms
// Allocation memory size: 7,58 GB      
```

## Некоторые свойства

#### A. Факториальное представление. 

**Формула 2**: \\(\binom{n}{k} = \frac{n!}{k!(n − k)!}\\), целое \\(n \geq\\) целого \\(k \geq 0\\).

Эта формула позволяет представлять комбинации факториалов в виде биномиальных коэффициентов, и наоборот.

#### B. Свойство симметрии. 

**Формула 3**: \\(\binom{n}{k} = \binom{n}{n - k}\\), целое \\(n \geq\\) целого \\(k \geq 0\\).

Эта формула справедлива для всех целых k. 
Если k отрицательно или больше, чем n, то биномиальный коэффициент равен нулю 
(при условии, что n — неотрицательное целое число).

#### C. Внесение-вынесение. 

**Формула 4**: \\(\binom{r}{k} = \frac{r}{k}\binom{r - 1}{k - 1}\\), целое \\(k != 0\\).

Эта формула очень полезна для комбинирования биномиального коэффициента с другими частями выражения.

Следствие формулы выше ещё одно соотношение:

**Формула 5**: \\(\binom{r}{k} = \frac{r}{r - k}\binom{r - 1}{k}\\)

#### D. Формула сложения. 

**Формула 6**: \\(\binom{r}{k} = \binom{r - 1}{k} + \binom{r - 1}{k - 1}\\), целое k,

> Каждое значение равно сумме двух значений из предыдущего ряда, 
> причем одно находится в том же столбце, а другое — в ближайшем столбце слева.

Формула может быть доказана, например, из формул **4** и **5**:

\\(r\binom{r - 1}{k} + r\binom{r - 1}{k - 1} = (r - k)\binom{r}{k} + k\binom{r}{k} = r\binom{r}{k}\\)

Формула сложения часто используется в доказательствах индукцией по r, когда r — целое число.

#### E. Формулы суммирования.

**Формула 7**: \\(\sum_{k=0}^{n}\binom{r+k}{k} = \binom{r}{0} + \binom{r + 1}{1} + ... + \binom{r + n}{n} = \binom{r + n + 1}{n}\\), целое \\(n \geq 0\\).

**Формула 8**: \\(\sum_{k=0}^{n}\binom{k}{m} = \binom{0}{m} + \binom{1}{m} + ... + \binom{n}{m} = \binom{n + 1}{m + 1}\\), целое \\(m \geq 0\\), целое \\(n \geq 0\\).

#### F. Биномиальная теорема.

**Формула 9**: \\((x + y)^{r} = \sum_{k}^{}\binom{r}{k}x^{k}y^{r-k}\\), целое \\(r \geq 0\\).

Частный случай формулы для y = 0:

**Формула 10**: \\(\sum_{k}^{}\binom{r}{k}x^{k} = (1 + x)^{r}\\), целое \\(r \geq 0\\) или \\(|x| < 1\\).

Обобщение формулы бинома:

**Формула 11**: \\((x + y)^{n} = \sum_{k}^{}\binom{n}{k}x(x - kz)^{k - 1}(y + kz)^{n - k}\\), целое \\(n \geq 0, x \neq 0\\).

#### G. Обращение верхнего индекса.

Следующее тождество непосредственно следует из определения биномиального коэффициента,
если каждый член числителя взять с противоположным знаком и умножить на (−1).

**Формула 12**: \\(\binom{r}{k} = (-1)^{k}\binom{k - r - 1}{k}\\), целое k.

Простым следствием соотношения выше является формула суммирования:

**Формула 13**: \\(\sum_{k \leq n}^{}\binom{r}{k}(-1)^{k} = \binom{r}{0} - \binom{r}{1} + ... + (-1)^n\binom{r}{n} = (-1)^n\binom{r - 1}{n}\\), целое n.

Для целого r можно получить еще одно важное следствие формулы:

**Формула 14**: \\(\binom{n}{m} = (-1)^{n-m}\binom{-(m + 1)}{n - m}\\), целое \\(n \geq 0\\), целое m.

Таким образом, можно переместить n из верхней позиции в нижнюю.

#### H. Упрощение произведений. 

Произведения биномиальных коэффициентов можно выразить несколькими различными способами, 
расписывая их через факториалы и снова возвращаясь к записи для биномиальных коэффициентов.
Например,

**Формула 15**: \\(\binom{r}{m}\binom{m}{k} = \binom{r}{k}\binom{r - k}{m - k}\\), целое m, целое k.

Формула выше очень полезна в случаях, когда индекс (а именно — m) находится 
и в верхней, и в нижней позициях, а нам нужно, чтобы он был только в одном месте.

#### I. Суммы произведений.

Следующие формулы показывают, чему равны суммы произведения двух биномиальных коэффициентов 
при различных положениях индекса суммирования k:

**Формула 16 (свертка Вандермонда)**: \\(\sum_{k}^{}\binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\\), целое n.

**Формула 17**: \\(\sum_{k}^{}\binom{r}{m + k}\binom{s}{n + k} = \binom{r + s}{r - m + n}\\), 
целое m, целое n, целое \\(r \geq 0\\).

**Формула 18**: \\(\sum_{k}^{}\binom{r}{k}\binom{s + k}{n}(-1)^{r-k} = \binom{s}{n - r}\\), целое n, целое \\(r \geq 0\\).

**Формула 19**: \\(\sum_{k=0}^{r}\binom{r-k}{m}\binom{s}{k - t}(-1)^{k-t} = \binom{r - t - s}{r - t - m}\\),
целое \\(t \geq 0\\), целое \\(r \geq 0\\), целое \\(m \geq 0\\).

**Формула 20**: \\(\sum_{k=0}^{r}\binom{r-k}{m}\binom{s + k}{n} = \binom{r + s + 1}{m + n + 1}\\),
целое \\(n \geq\\) целое \\(s \geq 0\\), целое \\(m \geq 0\\), целое \\(r \geq 0\\). 

**Формула 21**: \\(\sum_{k \geq 0}^{}\binom{r - tk}{k}\binom{s - t(n - k)}{n - k}\frac{r}{r - tk} = \binom{r + s - tn}{n}\\), целое n.

---

**Ссылки:**

- [The Art of Computer Programming - Donald E. Knuth, section 1.2.6](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
